Skip to main content

Bitwise AND of Numbers Range

LeetCode 201 | Difficulty: Medium​

Medium

Problem Description​

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

Constraints:

- `0 <= left <= right <= 2^31 - 1`

Topics: Bit Manipulation

Approach​

Bit Manipulation​

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

Solutions​

Solution 1: C# (Best: 80 ms)​

MetricValue
Runtime80 ms
MemoryN/A
Date2018-08-19
Solution
public class Solution {
    public int RangeBitwiseAnd(int m, int n) {
    if(m==0) return 0;
    int moveFactor = 0;
    while(m!=n)
    {
        m = m>>1;
        n = n>>1;
        moveFactor++;
    }
    return m<<moveFactor;
    }
}

Complexity Analysis​

ApproachTimeSpace
Bit Manipulation$O(n) or O(1)$$O(1)$

Interview Tips​

Key Points
  • Discuss the brute force approach first, then optimize. Explain your thought process.